//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
//
//
// 示例 2：
//
//
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 8
// -10 <= nums[i] <= 10
//
//
// Related Topics 数组与矩阵 回溯与递归 👍 1357 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function permuteUnique(nums: number[]): number[][] {

    function backtracking(temp) {
        if (temp.length === nums.length) {
            res.push(temp.slice())
            return
        }
        for (let i = 0; i < nums.length; i ++) {
            if (i > 0 && nums[i] === nums[i - 1] && usedArr[i - 1] === false) continue;
            if (usedArr[i] === false) {
                temp.push(nums[i])
                usedArr[i] = true
                backtracking(temp)
                usedArr[i] = false
                temp.pop()
            }
        }
    }
    let res : number[][] = []
    //? 对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
    const usedArr: boolean[] = new Array(nums.length).fill(false);
    nums.sort((a, b) => a - b)
    backtracking([])
    return res
};
//leetcode submit region end(Prohibit modification and deletion)
//? set版
function permuteUnique2(nums: number[]): number[][] {

    function backTracking(route: number[],set = new Set()): void {
        if (route.length === nums.length) {
            resArr.push([...route]);
            return;
        }
        for (let i = 0, length = nums.length; i < length; i++) {
            //? 去重判断  usedArr是是否使用过的记录数组，只会限制同一树层而不会限制递归
            if (i > 0 && nums[i] === nums[i - 1] && !set.has(i - 1)) continue;
            if (!set.has(i)) {
                route.push(nums[i]);
                set.add(i)
                backTracking(route,set);
                route.pop()
                set.delete(i)
            }
        }
    }
    nums.sort((a, b) => a - b);
    const resArr: number[][] = [];
    // const usedArr: boolean[] = new Array(nums.length).fill(false);
    backTracking([]);
    return resArr;
};
